Traffic flows in a modern large-scale network may often be subjected to ill-considered policy-based mechanisms intended to “shape” that traffic. Often, such policy-driven traffic shaping is detrimental to encrypted flows, even when such flows would ordinarily not get “shaped” if not for the encryption.
Furthermore, in some global regions, traffic that is encrypted is often subjected to more scrutiny by invasive surveillance techniques than would be the case if the traffic wasn't encrypted. In effect, the encrypted traffic, even if it is “innocuous,” can attract undue attention merely because of the encryption.
At many places in the modern Internet, particularly near the network edge, traffic-shaping technology has been designed to automatically detect encrypted flows and treat these flows differently according to local policy. Such treatment may actually include dropping the traffic or placing this traffic in a Quality of Service (“QOS”) queue that has a very low priority.
Encrypted traffic, with the exception of fixed headers, has the peculiar statistical property of being indistinguishable from a strong pseudo-random sequence of the same length. However, if encrypted traffic observed is over a sufficiently long time interval, a very uniform distribution of bits, or octets, occurs which can generally render this traffic distinguishable from non-encrypted traffic. It is precisely this property that allows traffic-shaping hardware to identify encrypted flows, and execute “policy” on those flows. Flows that are not encrypted have a very different statistical distribution of bits (octets) than those flows that are encrypted.
Several tests may be performed on traffic to determine if that traffic has the statistical properties of encrypted traffic. All encrypted traffic will pass those tests, although passing those tests does not necessarily indicate the presence of encryption. For example, traffic flows that have been compressed have long-term statistical properties that are nearly indistinguishable from those of random or encrypted flows.
A common test suite for randomness can usually indicate whether that traffic is encrypted or not. A suite such as that described in Federal Information Processing Standards (“FIPS”) 140-2 can reliably distinguish random-looking flows from those that do not appear random, usually with as little as 4 Kbytes of traffic from the flow.
Similarly, over the longer term, attempting to compress the contents of the flow using any one of a number of compression functions can be used to distinguish random-type flows from those flows that are not random. For example, attempting to compress a purely-random flow results in no compression, or even size inflation, depending on the compression algorithm used. Flows that are non-random will tend to be moderately-to-strongly compressible.
There is historical support for the use of steganography to hide secret communications, in such a way that only the sender and the intended recipient even realize there is a hidden message. Thus, it seems natural and tempting to use steganographic techniques to hide the random-looking bits of an encrypted flow inside something that looks statistically non-encrypted.
It has been suggested that some groups hide encrypted messages inside such innocuous objects as digital image files on the Internet, using them as a low-bandwidth communications technique. There are various tools extant that assist in the creation of steganographic materials, using audio, video, and image files as the “carriers” for steganographically-hidden information.
However, the bandwidth efficiency of “traditional” steganography techniques is typically very low, with the “carrier” information dominating the bandwidth used in communicating steganographic objects. Ratios of the carrier information to hidden information on the order of 100:1 or worse are not uncommon using this technique. Nevertheless, an advantage of steganographic techniques is that the resulting data flows have distinctly non-uniform statistical distributions of octets, which means that they are unlikely to be identified as encrypted traffic by automated mechanisms within the Internet.
It is also possible to encode encrypted bit-streams so that they look like, for example, ordinary English text. Techniques such as using a dictionary of common English words to represent groupings of cipher text bits have historically been used to hide the existence of an underlying encrypted message. For example, if groups of four bits are considered at one time, they may be used as an “index” into a short array of English (or German, Spanish, French, etc) words. Those words are substituted for the bit-sequence, and the receiver simply looks up the corresponding bit-sequence when they encounter one of the dictionary items. The technique is quite effective at fooling automated tests for randomness, particularly if those tests are unaware of the existence of the bits-to-English substitution mapping, and if that mapping is sufficiently large.
Problems arise when communication bandwidth efficiency is a strong consideration in the development of a coding system to hide encrypted flows. The system described above, for example, requires substantial overhead to represent 4 bits of “real” information. Typically, between 40 and 50 bits are transmitted in order to represent those 4 bits of actual information.
Many encoding techniques exist that are used to translate binary data into codings that are suitable for highly-constrained channels, such as e-mail ASCII transfer, etc. These codings are relatively bandwidth-efficient, producing a 30% increase in occupied bandwidth. Many protocols in use on the Internet today use some variant of the Base64 coding which translates 24 bits of input data into 32 bits of output data with strong constraints on the output alphabet. However, codings that are based on Base64 can be readily identified in an automated fashion, which means that the encoding can be removed, with the resulting bit-stream further analyzed for randomness.
A key concept in reducing detectability of encrypted flows is to reduce the information density of the encrypted flow. An encrypted data flow appears to be a strong pseudo-random sequence, which means that it has maximal information density, or minimal redundancy. Any technique that reduces the amount of information carried per transmitted bit consequently reduces the probability of detection of the resulting flow as a strong pseudo-random, and therefore, probably an encrypted flow.
Standard encodings, such as Base64 reduce the information carried per transmitted bit. But, because Base64 is easily recognized, it may be decoded and the resulting bit sequence analyzed for randomness. Therefore, what is needed is a system and method of coding that simultaneously reduces the information density of a traffic flow and reduces the probability of detecting the coding scheme so that the traffic is not detected as being encrypted and so that the traffic is not analyzed based on the detection of the coding scheme.